//==============================================================================
//	 GraphTable.hh
//
//------------------------------------------------------------------------------
// $Id:$
//------------------------------------------------------------------------------
// $Log:$
//==============================================================================
//.......1.........2.........3.........4.........5.........6.........7.........8
//

#ifndef _GRAPH_TABLE
#define _GRAPH_TABLE

#include "LocalSTL.hh"
#include "Table.hh"

const float MAX_EDGE_WEIGHT = 99999;

//------------------------------------------------------------------------------
// * GraphTable
//------------------------------------------------------------------------------
// Performs algorithms on graphs in adjacency matrix format.  Need to use a more
// efficient table class than Table, something based on valarray.   
// 
//
class GraphTable: public Table<float>{
public:
 
  GraphTable(string FileName){
	 this->ReadWithLabels(FileName);
  };

  GraphTable(char* FileName){
	 string temp = FileName;
	 this->ReadWithLabels(temp);
  };

  GraphTable(int rows,int cols){
	 Allocate(rows,cols);
  }

  void ComputeAllPairsShortestPath();
  void ComputeAllPairsShortestPath(float Bound);
  void PrintShortestPath(ostream &fout,int Start,int End);


  void GetShortestPath(int i, int j, Table<int> &PD,vector<int> &p){
	 if (i == j){
		p.push_back(i);
		return;
	 }else{
		if (PD[i][j] == -1){
		  return;// No path. 
		}else{
		  GetShortestPath(i,PD[i][j],PD,p);
		  p.push_back(j);
		}
	 }
  }

  void GetShortestPath(int Start,int End,vector<int> &path){
	 GetShortestPath(Start,End,mPredecessorMatrix,path);	 
  }

  float  PathLength(int start, int end){
	 return(mWeightMatrix[start][end]);
  }

  void PrintPathMatrix(ostream &fout){
	 mWeightMatrix.Print(fout);
  }

protected:

  void FloydWarshall(Table<float> &TableIn,Table<int> &PredecessorIn);
  void GetShortestPathNodes(int &Start,int &End);
  void PrintShortestPath(ostream &fout,int Start,int End,Table<int> &PD);

  Table<int> mPredecessorMatrix;
  Table<float> mWeightMatrix;

};

#endif
